package Hot100.leetcode.editor.cn.code.二分;

import java.util.Arrays;

//Java：统计公平数对的数目
public class CountTheNumberOfFairPairs{
    public static void main(String[] args) {
        Solution solution = new CountTheNumberOfFairPairs().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public long countFairPairs(int[] nums, int lower, int upper) {
            Arrays.sort(nums);
            long ans = 0;
            for (int j = 0; j < nums.length; j++) {
                // 在 [0, j-1] 范围内查找满足 nums[i] + nums[j] 在 [lower, upper] 的 i
                int r = lowerBound(nums, j, upper - nums[j] + 1);
                int l = lowerBound(nums, j, lower - nums[j]);
                ans += r - l;
            }
            return ans;
        }
        //左闭右闭
        private int lowerBound(int[] nums, int left, int target) {
            int right = nums.length - 1;
            while (left <= right) {
                int mid = (left + right) >>> 1;
                if (nums[mid] >= target) {
                    right = mid-1;
                } else {
                    left = mid+1;
                }

            }
            return left;
        }
        //返回数组中第一个大于等于target的元素索引 左闭右开区间
        private int lowerBound1(int[] nums, int right, int target) {
            int left = 0;
            while (left < right) {
                int mid = (right + left) >>> 1;
                if (nums[mid] >= target) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return right;
        }

    }

//leetcode submit region end(Prohibit modification and deletion)

}